import java.util.*;


public class TreeExample {


	public static TreeNode buildTree() {
		TreeNode a = new TreeNode("A");
		TreeNode b = new TreeNode("B");
		TreeNode c = new TreeNode("C");
		TreeNode d = new TreeNode("D");
		TreeNode e = new TreeNode("E");
		TreeNode f = new TreeNode("F");
		TreeNode g = new TreeNode("G");
		TreeNode h = new TreeNode("H");
		TreeNode i = new TreeNode("I");
		TreeNode j = new TreeNode("J");
		TreeNode k = new TreeNode("K");

		a.insertChild(null, b);
		a.insertChild(b, c);
		a.insertChild(c, d);
		a.insertChild(d, e);

		b.insertChild(null, f);
		b.insertChild(f, g);

		d.insertChild(null, h);

		e.insertChild(null, i);
		e.insertChild(i, j);

		j.insertChild(null, k);

		return a;
	}


	public static int height( TreeNode tree ) {
        
		int maxChildHeight = -1;
		
		TreeNode child = tree.firstChild;

		while (child != null) {
		
			int childHeight = height(child);

			if (childHeight > maxChildHeight) {
				maxChildHeight = childHeight;
			}

			child = child.nextSibling;
		}

		return maxChildHeight + 1;
	}

	
	public static void print( TreeNode tree ) {
		print(tree, 0);
	}

	private static void print( TreeNode tree, int depth ) {
		
		indent(depth);

		System.out.println(tree.element);

		TreeNode child = tree.firstChild;

		while (child != null) {

			print(child, depth + 1);

			child = child.nextSibling;
		}
	}

	private static void indent(int depth) {
		for (int i=0; i < depth; ++i) {
			System.out.print(" ");
		}
	}


	public static void main(String[] args) {
		TreeNode tree = buildTree();

		System.out.println("\n\nheight = " + height( tree ) );

		print(tree);
		
        System.out.print("\n\nPre-Order: ");
        preOrderTraversal(tree);

        System.out.print("\n\nPost-Order: ");
        postOrderTraversal(tree);

        System.out.print("\n\nLevel-Order: ");
        levelOrderTraversal(tree);

        System.out.print("\n\nMystery-Order: ");
        mysteryOrderTraversal(tree);
	}

	
	private static void processNode( TreeNode tree ) {

		System.out.print(tree.element + " ");
	}

	
    public static void preOrderTraversal(TreeNode tree) {

		processNode(tree);

		TreeNode child = tree.firstChild;

		while (child != null) {

			preOrderTraversal(child);

			child = child.nextSibling;
		}
    }


    public static void postOrderTraversal(TreeNode tree) {

		TreeNode child = tree.firstChild;

		while (child != null) {

			postOrderTraversal(child);

			child = child.nextSibling;
		}

		processNode(tree);
    }

	
    public static void levelOrderTraversal(TreeNode tree) {

		Queue q = new LinkedList();

		q.offer(tree);

		while (!q.isEmpty()) {
		
			TreeNode n = (TreeNode)q.poll();

			processNode(n);

			TreeNode child = n.firstChild;

			while (child != null) {
			
				q.offer(child);
				
				child = child.nextSibling;
			}
		}

    }

	
	public static void mysteryOrderTraversal(TreeNode tree) {

		Stack stack = new Stack();

		stack.push(tree);

		while (!stack.isEmpty()) {
		
			TreeNode n = (TreeNode)stack.pop();

			processNode(n);

			// add children (results in a reverse pre-order traversal)
			TreeNode child = n.firstChild;

			while (child != null) {
			
				stack.push(child);
				
				child = child.nextSibling;
			}

			// call this instead to get a pre-order traversal
			//mysteryAddChildren(stack, n.firstChild);
		}
	}


	private static void mysteryAddChildren(Stack stack, TreeNode child) {
		
		if (child != null) {
			mysteryAddChildren(stack, child.nextSibling);
			stack.push(child);
		}
	}


}